/* Author: DO HOANG HAI
 * Main.java
 *
 * Created on June 4, 2006, 9:01 PM
 *
 * this project demonstrate how to use bread-first-search to find tha the destinatiion from a starting node
 */

package bfs;
import java.util.Scanner;
import java.io.*;
import java.io.FileNotFoundException;
import javax.crypto.NullCipher;

/**
 *
 * @author hai
 */
public class Main {
    
    
    private static int[][] dis=new int[8][8];
    private static int numOfNode;
    /** Creates a new instance of Main */
    public Main() {
    }
    
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        readData();
        System.out.println();
         Scanner input=new Scanner(System.in);
        System.out.println("Id of the root node: ");
        int rootId=input.nextInt();
        System.out.println("Id of the destination node: ");
        int desId=input.nextInt();
        
        int[] result = startSearch(rootId, desId);
        for (int i=0; i< result.length; i++)
        {
            System.out.print("  " + result[i]);
        }
        System.out.println();
    }
    
    public static void readData(){
        try{
            Scanner reader=new Scanner(new File("src/testData.txt"));
            int i=0;
           
            while(reader.hasNextLine()){
                int j=0;
                String aLine=reader.nextLine();
                Scanner extractLine=new Scanner(aLine);
                while(extractLine.hasNext()){
                    dis[i][j]=extractLine.nextInt();
                    j++;
                }
                
                i++;
            }
            numOfNode=i;
            for (int m=0; m<numOfNode; m++){
                for (int n=0; n<numOfNode; n++)
                    System.out.print("  "+dis[m][n]);
                System.out.println();
            }
            reader.close();
            
            
        }
        catch(FileNotFoundException e){
            System.out.println("File is not found");
        }
        
    }
    public static int[] startSearch(int rootId, int desId)
    {
        int[] result = new int[dis.length];
        if (rootId == desId)
        {
            result[0]  = rootId;
            return result;
        }
        else
        {
             queue q = new queue(dis.length);
             Node[] arOfNodes = new Node[dis.length];
             for (int i = 0; i<dis.length; i++){
                 arOfNodes[i] = new Node(i);                         
             }
             
             q.add(arOfNodes[rootId]);
             arOfNodes[rootId].visited  = true;
             result[0] = rootId;
             Node curNode;
             int resultIndex = 1;
             do{
                 curNode =   (Node)q.remove();                 
                 for (int i = 0; i< dis.length; i++)
                 {
                     if (!arOfNodes[i].visited && dis[curNode.id][arOfNodes[i].id]!=0)
                     {
                         q.add(arOfNodes[i]);
                         arOfNodes[i].visited = true;
                         result[resultIndex] = arOfNodes[i].id;
                         resultIndex++;
                         //System.out.print("  " + arOfNodes[i].id);
                         if (arOfNodes[i].id == desId)
                             return result;
                     }
                     
                 }
             } while (!q.isEmpty());    
         
             if (q.isEmpty())
                 return new int[0];
             
        }
        return result;
         
    }
    
}
class Node{
    public boolean visited = false;
    int id;
    public Node(int id){
        this.id= id;
    }   
}
class queue 
{
    Object[] ar;
    private int last = 0;
    private int numberOfElements = 0;
    public queue(int maxNumber)
    {
        super();
        ar = new Object[maxNumber];
       // for (int i = 0; i<maxNumber; i++)
       // {
       //     ar[i] = new Object();
       // }
    
    }
    public void clear() {
        for (int i = 0; i<=last; i++){
            ar[i] = null;            
        }
    }
    
    public boolean isEmpty() {
        return numberOfElements == 0;        
    }

    public Object peek() {
        return ar[0];
    }

    public Object remove() {
        if (numberOfElements>0)
        {
             Object temp = ar[0];
             for (int i = 0; i< last; i++)
             {
                 ar[i] = ar[i+1];
                 numberOfElements--;
                 last--;
             }
            ar[last+1] = null;
            return temp;
        }
        else
            return null;
       
    }

    public int size() {
        return last;
    }

    public boolean add(Object obj ) {
        if (last < ar.length-1)
        {
            ar[last] = obj;
            last++;
            numberOfElements++;    
            return true;
        }
        else return false;
        
    }

    
    

}
